package Offer.offer2017;

/**
 * 圆圈中最后剩下的数字 约瑟夫环
 * @author: leiwenkang
 * @date: 2020/5/31
 * @time: 11:17
 */
public class Test45 {
    public int LastRemaining_Solution(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }

        int[] array = new int[n];

        int index = -1;
        int step = 0;
        int count = n;

        while (count > 0) {
            index++;
            if (index >= n) {
                index = 0;
            }
            if (array[index] == -1) {
                continue;
            }
            step++;
            if (step == m) {
                array[index] = - 1;
                step = 0;
                count--;
            }
        }
        return index;
    }

    public int LastRemaining_Solution2(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }

        if (n == 1) {
            return 0;
        }

        return (LastRemaining_Solution2(n - 1, m) + m) % n;
    }
}
